package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/29 18:09
 * @Description:寻找BST中第K个最小元素-中序遍历的常规解法，时间复杂度O(n)
 * 另一种思路，如果能在每个节点内部记录以当前root为根的BST有多少节点个数size
 * 通过和root.left.size就能知道当前节点的排序，可以做到在O(logn)时间内找到第k小节点
 */
public class Num230_FindKSmall {
    int i = 0;
    int res = 0;
    public int kthSmallest(TreeNode root, int k) {
        traverse(root,k);
        return res;
    }
    private void traverse(TreeNode root, int k) {
        // base case
        if (root == null) {
            return;
        }
        traverse(root.left,k);
        // 中序位置
        i ++;
        if (i == k) {
            // 当前节点就是要输出的节点
            res = root.val;
            return;
        }
        traverse(root.right,k);
    }
}
